%  _   _                           _
% | | | |                         (_)
% | |_| | __ _ _ __ ___  _ __ ___  _ _ __   __ _
% |  _  |/ _` | '_ ` _ \| '_ ` _ \| | '_ \ / _` |
% | | | | (_| | | | | | | | | | | | | | | | (_| |
% \_| |_/\__,_|_| |_| |_|_| |_| |_|_|_| |_|\__, |
%                                           __/ |
%                                          |___/

distHam([],[],0).
		% Caso base.
distHam([X|Xs], [X|Ys], R) :- member(X, [0,1]), distHam(Xs, Ys, R).
		% Si ambas listas tienen el mismo primer elemento,
		% puedo mirar la distancha de hamilton de sus
		% respectivas colas
		% (por la definición de distancia de Hamilton,
		% la distancia sería "0+distHam(Xs,Ys)".
distHam([X|Xs], [Y|Ys], R) :-  member(X, [0,1]), member(Y, [0,1]),
								X\=Y,
								distHam(Xs, Ys,
								Q), R is Q + 1.
		% Si los primeros elementos de ambas listas son
		%distintos (y ambos son 0 o 1), entonces sumamos 1
		%a la distancia de Hamilton entre sus colas. 
		%Ahora no obviamos el "1 +"

% ______	  __ _ _
% | ___ \	 / _(_|_)
% | |_/ / __ ___| |_ _ _  ___  ___
% |  __/ '__/ _ \  _| | |/ _ \/ __|
% | |  | | |  __/ | | | | (_) \__ \
% \_|  |_|  \___|_| |_| |\___/|___/
%		     _/ |
%		    |__/

% Función Auxiliar "hastaNDigitos01(+N,?S)".
		% Esta función toma un número (instanciado) y una
		% lista (posiblemente instanciada).
		% Si la lista no está instanciada, entonces genera
		% las 2^n listas de 0s y 1s de longitud n.
		% Si la lista está instanciada, entonces verifica
		% que la lista tenga
		% longitud n y todos sus elementos sean 0 o 1.
hastaNDigitos01(0,[]).
hastaNDigitos01(N,[D|Ds]) :- N > 0, member(D,[0,1]), N1 is N - 1,
								hastaNDigitos01(N1,Ds).

% Función Auxiliar "TodosHasta(+N,?S)".
			% Esta función toma un número (instanciado) y una
			% lista (posiblemente instanciada).
			% Si la lista no está instanciada, entonces genera
			% todas las listas de 0s y 1s de longitud menor o
			% igual a n.
			% Si la lista está instanciada, entonces verifica
			% que la lista tenga
			% longitud menor o igual a n y todos sus elementos
			% sean 0 o 1.
todosHasta(N,S) :- between(0,N,Z), hastaNDigitos01(Z,S).

% Función Auxiliar "sonTodos01(?S)".
			% Esta función toma una lista (posiblemente
			% instanciada).
			% Si la lista no está instanciada, genera las
			% infinitas listas, en forma ordenada de 0s y 1s.
			% Si la lista está instanciada, verifica que todos
			% sus elementos sean 0 o 1.
sonTodos01(Xs) :- length(Xs,X), hastaNDigitos01(X,Xs).

%Función Auxiliar "longPrefijoComun(+X,?Y,?N)".
			% Esta función toma dos listas (la primera instanciada
			% y la segunda
			% posiblemente instanciada) y un número (posiblemente
			% instanciado).
			% Si ambas listas están instanciadas, devuelve el
			% N la longitud del
			% prefijo común más largo entre ambas listas (o,
			% si N también está
			% instanciado, verifica que sea).
longPrefijoComun([],_,0).
			% La longitud de prefijo común entre cualquier
			% lista y la lista vacía es 0.
longPrefijoComun(X,[],0) :- length(X,N),N > 0.
			% Caso análogo al anterior, pero verificando que
			% la lista no sea vacía. Esto es
			% para evitar respuestas duplicadas (por ejemplo,
			% que longPrefijoComun([],[],0)
			% devuelva "true" dos veces).
longPrefijoComun([X|_],[Y|_],0) :- member(X,[0,1]), member(Y,[0,1]), X\==Y.
			% Si los primeros elementos de ambas listas son
			% distintos, entonces
			% el prefijo común más largo es 0.
longPrefijoComun([X|Xs],[X|Ys],R) :- member(X,[0,1]), longPrefijoComun(Xs,Ys,Q),
										R is Q+1.
			% Si los primeros elementos de ambas listas son
			% iguales, entonces
			% la longitud del prefijo común más largo es 1 +
			% la longitud del
			% prefijo común de sus respectivas colas.

%Función Auxiliar "soyUnaListaDeCerosYUnos(+S)".
			% Acá viene la magia.
			% Esta función verifica que una lista esté compuesta
			% enteramente
			% de 0s y 1s, pero de forma más fuerte porque,
			% además, verifica
			% que la lista sea efectivamente una lista.
			% Para eso, se usa la función "member(S,[[X|Xs]])",
			% que se fija
			% si S pertenece a la lista formada por toda posible
			% lista de
			% longitud mayor o igual que 1.
soyUnaListaDeCerosYUnos([]).
soyUnaListaDeCerosYUnos(S) :- member(S,[[X|Xs]]), var(X), var(Xs).
soyUnaListaDeCerosYUnos(S) :- member(S,[[X|Xs]]), not(var(X)),
								member(X,[0,1]), var(Xs).
soyUnaListaDeCerosYUnos(S) :- member(S,[[X|Xs]]), var(X), not(var(Xs)),
								soyUnaListaDeCerosYUnos(Xs).
soyUnaListaDeCerosYUnos(S) :- member(S,[[X|Xs]]), not(var(X)), member(X,[0,1]),
								not(var(Xs)), soyUnaListaDeCerosYUnos(Xs).

% Función de Distancia de Prefijos
distPref(Xs,Ys,R) :- not(ground(R)), ground(Ys), sonTodos01(Xs),
						sonTodos01(Ys),
						length(Xs,X), length(Ys,Y),
						longPrefijoComun(Xs,Ys,P),
						R is X + Y - P - P.
			% Si R no está instanciado:
			% Verifico que la primer lista esté enteramente
			% compuesta de 0s y 1s.
			% Si la segunda lista está instanciada, verifico
			% que esté compuesta de 0s y 1s.
			% Calculo la distancia de prefijos como la suma de
			% ambas longitudes menos
			% dos veces la longitud del prefijo común más
			% largo	entre ambas.

distPref(Xs,Ys,R) :- not(ground(R)), not(ground(Ys)), sonTodos01(Xs),
						soyUnaListaDeCerosYUnos(Ys), sonTodos01(Ys),
						length(Xs,X), length(Ys,Y),
						longPrefijoComun(Xs,Ys,P),
						R is X + Y - P - P.

distPref(Xs,Ys,R) :- ground(R), length(Xs,X), L is R+X+X , sonTodos01(Xs),
						todosHasta(L,Ys), length(Ys,Y),
						longPrefijoComun(Xs,Ys,P),
						R is X + Y - P - P.
			% Si R está instanciado:
			% Verifico que la primer lista esté enteramente
			% compuesta de 0s y 1s.
			% Si Ys no está instanciada, genero todas las listas
			% de 0s y 1s de
			% longitud menor o igual a R + 2 veces la longitud
			% de la primer lista (cota).
			% Si Ys está instanciada, verifico que esté
			% enteramente compuesta de 0s y 1s,
			% y que su longitud sea menor a R + 2 veces la
			% longitud de la primer lista.
			% Calculo la distancia de prefijos como la suma de
			% ambas longitudes menos
			% dos veces la longitud del prefijo común más
			% largo	entre ambas.

%  _____    _ _      _
% |  ___|  | (_)    (_)
% | |__  __| |_  ___ _	___  _ __
% |  __|/ _` | |/ __| |/ _ \| '_ \
% | |__| (_| | | (__| | (_) | | | |
% \____/\__,_|_|\___|_|\___/|_| |_|


%Función Auxiliar "calcDistEd(+S,+T,?N)".
%Esta funcion realiza la recurrencia como esta incluida en el trabajo practico,
%asumiendo que ambas listas estan instanciadas (con lo cual hay que ejecutar la
%recurrencia nada mas).
calcDistEd([],T,N) :- length(T,N),!.
calcDistEd(S,[],N) :- length(S,N),!.
calcDistEd([X|Y],[X|Z],R) :- calcDistEd(Y,Z,R),!.
calcDistEd([A|Y],[B|Z],R) :- A \= B,calcDistEd([A|Y],Z,P),
								calcDistEd(Y,Z,S),
								calcDistEd(Y,[B|Z],Q),
								R is min(S,min(P,Q))+1, !.

distEd(S,T,N) :- soyUnaListaDeCerosYUnos(S), ground(T),
					sonTodos01(T),calcDistEd(S,T,N).

distEd(S,T,N) :- soyUnaListaDeCerosYUnos(S), not(ground(T)), ground(N),
					length(S,Q), R is Q+N, todosHasta(R,T),
					calcDistEd(S,T,N).

distEd(S,T,N) :- soyUnaListaDeCerosYUnos(S), not(ground(T)), not(ground(N)),
					soyUnaListaDeCerosYUnos(T),
					length(T,R), todosHasta(R,T),
					calcDistEd(S,T,N).
